package com.atguigu.distributed.lock.leecode.tree;

import com.atguigu.distributed.lock.leecode.ListNode;
import com.atguigu.distributed.lock.leecode.TreeNode;

/**
 * 力扣中等109有序链表转换二叉搜索树
 * 给定一个单链表的头节点  head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。
 * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1
 */
public class SortedListToBST {
    public TreeNode sortedListToBST(ListNode head){
        return buildTree(head,null);
    }
    public TreeNode buildTree(ListNode left,ListNode right){
        if(left==right){
            return null;
        }
        ListNode mid = getMedian(left,right);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(left,mid);
        root.right = buildTree(mid.next,right);
        return root;
    }
    public ListNode getMedian(ListNode left,ListNode right){
        ListNode fast = left;
        ListNode slow = left;
        while (fast!=right&&fast.next!=right){
            fast = fast.next;
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

}
